128. Longest Consecutive Sequence.c

/*
128. Longest Consecutive Sequence

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.


For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.


Your algorithm should run in O(n) complexity.
*/

typedefstructe_s {
intkey;
intlen;
structe_s*shadow;
} e_t;

#defineHSZ 1000

voidput(e_t**htable, intkey, intlen) {
e_t*e=malloc(sizeof(e_t));
//assert(e);
e->key=key;
e->len=len;
e->shadow=htable[key % HSZ];
htable[key % HSZ] =e;
}

intlookup(e_t**htable, intkey, int**lp) {
e_t*e=htable[key % HSZ];
// Runtime Error Message:
// Line 20: member access within misaligned address 0x000001ea62f4 for type 'struct e_t', 
// which requires 8 byte alignment
while (e&&e->key!=key) {
e=e->shadow;
 }
if (e) {
*lp=&e->len;
returne->len;
 }
return0;
}

intlongestConsecutive(int*nums, intnumsSize) {
inti, l, r, x, len=0;
e_t*htable[HSZ] = { 0 };
int*llp, *rlp;

// make a hash table to store the length of consecutive of current number
// and update the length of consecutive of left and right boundary

for (i=0; i<numsSize; i++) {
if (lookup(htable, nums[i], &llp) ==0) {
l=lookup(htable, nums[i] -1, &llp);
r=lookup(htable, nums[i] +1, &rlp);
x=l+r+1;

put(htable, nums[i], x);
if (l) *llp=x;
if (r) *rlp=x;

if (len<x) len=x;
 }
 }

// TODO: clean up memory

returnlen;
}

/*
Difficulty:Hard
Total Accepted:109K
Total Submissions:296.1K


Companies Google Facebook
Related Topics Array Union Find
Similar Questions 


 Binary Tree Longest Consecutive Sequence
*/